#include <iostream>
#include <ctime>

const int capacity = 10;
class MinHeap
{
public:
    MinHeap():size(0){}
    void Insert(int value)
    {
        if(size == capacity)
            return;
        array[size] = value;
        SifwUp(size);
        size++;
    }

    void Remove()
    {
        if(size == 0)
            return;
        array[0] = array[--size];
        SiftDown(0);
    }
    int * GetRoot()
    {
        if(size == 0)
            return nullptr;
        return &array[0];
    }

    void show()
    {
        for(int i = 0;i < size;i++)
            std::cout<<array[i]<<" ";
        std::cout<<std::endl;
    }
private:
    int GetParent(int i){return (i-1)/2;}
    int GetLeftChild(int i){return 2*i +1;}
    int GetRightChild(int i){return 2*i + 2;}

     void SifwUp(int i)
    {
        while(i > 0 && array[i] < array[GetParent(i)]) //O(logn)
        {
            std::swap(array[i],array[GetParent(i)]);
            i = GetParent(i);
        }
    }

    void SiftDown(int i)
    {
        int left = GetLeftChild(i);
        int right = GetRightChild(i);
        int max = i;
        if(left < size && array[left] < array[max])
        {
            max = left;
        }
        if(right < size && array[right] < array[max])
        {
            max = right;
        }
        if(max != i)//i下沉
        {
            std::swap(array[i],array[max]);
            SiftDown(max);//递归下沉
        }
    }

    int array[capacity];
    int size;

};

int main()
{
    int a[20] = {0};
    for(int i = 0;i < 20;i++)
    {
        a[i] = std::rand() % 100 ;
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
    MinHeap h;
    for(int i = 0;i < 5;i++)
    {
        h.Insert(a[i]);
    }
     for (size_t i = 5; i < 20; i++)
    {
        if(a[i] > *h.GetRoot())
        {
            h.Insert(a[i]);
            h.Remove();
        }
    }
    //h.Remove();
    h.show();


    return 0;
}